import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class StackMain {
    public static void main(String[] args) {
        // 1. 初始化数据：A数组用顺序栈存储，B数组用链栈存储
        Integer[] arrayA = {9, 19, 29, 39, 49, 59, 69, 79};
        Integer[] arrayB = {8, 18, 28, 38, 48, 58, 68, 78, 98};

        // 2. 顺序栈操作（存储arrayA）
        StackInterface<Integer> arrayStack = new ArrayStack<>(arrayA.length);
        System.out.println("=== 顺序栈（存储数组A）操作 ===");
        // 入栈
        for (int num : arrayA) {
            arrayStack.push(num);
            System.out.println("入栈元素：" + num + "，当前栈顶：" + arrayStack.peek());
        }
        // 出栈（暂存出栈元素，用于后续合并）
        List<Integer> listA = new ArrayList<>();
        while (!arrayStack.isEmpty()) {
            int popNum = arrayStack.pop();
            listA.add(popNum);
            System.out.println("出栈元素：" + popNum + "，出栈后栈是否为空：" + arrayStack.isEmpty());
        }

        // 3. 链栈操作（存储arrayB）
        StackInterface<Integer> linkedStack = new LinkedStack<>();
        System.out.println("\n=== 链栈（存储数组B）操作 ===");
        // 入栈
        for (int num : arrayB) {
            linkedStack.push(num);
            System.out.println("入栈元素：" + num + "，当前栈顶：" + linkedStack.peek());
        }
        // 出栈（暂存出栈元素，用于后续合并）
        List<Integer> listB = new ArrayList<>();
        while (!linkedStack.isEmpty()) {
            int popNum = linkedStack.pop();
            listB.add(popNum);
            System.out.println("出栈元素：" + popNum + "，出栈后栈是否为空：" + linkedStack.isEmpty());
        }

        // 4. 合并数据并排序（从小到大）
        List<Integer> mergedList = new ArrayList<>();
        mergedList.addAll(listA);
        mergedList.addAll(listB);
        Collections.sort(mergedList); // 从小到大排序

        // 5. 有序数据入栈（使用链栈，无需考虑容量）
        StackInterface<Integer> sortedStack = new LinkedStack<>();
        for (int num : mergedList) {
            sortedStack.push(num);
        }

        // 6. 输出有序栈（出栈顺序即从小到大）
        System.out.println("\n=== 合并后从小到大的有序栈输出 ===");
        System.out.print("有序栈元素（从小到大）：");
        while (!sortedStack.isEmpty()) {
            System.out.print(sortedStack.pop() + " ");
        }
    }
}